#pragma once
#include <iostream>
#include <vector>
#include <cassert>

namespace link_hash
{
    const int default_capacity = 10;

    template <class T>
    struct HashNode
    {
    public:
        T _val;
        HashNode<T>* _next;

        HashNode(const T& val) : _val(val), _next(nullptr)
        {}
    };

    template <class K, class T, class KeyOfT>
    class HashTable;

    template <class K, class T, class Ref, class Ptr, class KeyOfT>
    struct HTIterator
    {
    public:
        typedef HashNode<T> Node;
        
        HashTable<K, T, KeyOfT>* _pht;
        Node* _node;

        HTIterator(Node* node, HashTable<K, T, KeyOfT>* pht) : _node(node), _pht(pht)
        {}

        Ref operator*()
        {
            return _node->_val;
        }

        Ptr operator->()
        {
            return &_node->_val;
        }

        HTIterator& operator++()
        {
            assert(_node);
            if(_node->_next)
                _node = _node->_next;
            else
            {
                int index = _node->_val.first % _pht->size();
                int i = 0;
                for(i = index + 1;i < _pht->_table.size();++i)
                {
                    if(_pht->_table[i])
                    {
                        _node = _pht->_table[i]; 
                        break;
                    }
                }
                if(i == _pht->_table.size())
                    _node = nullptr;
            }

            return *this;
        }

        bool operator==(const HTIterator& lt) const
        {
            return _node == lt._node;
        }

        bool operator!=(const HTIterator& lt) const
        {
            return _node != lt._node;
        }
    };

    template <class K, class T, class KeyOfT>
    class HashTable
    {
    public:
        typedef HTIterator<K, T, T&, T*, KeyOfT> iterator;
    
        iterator begin()
        {
            for(int i = 0;i < _table.size();++i)
            {
                if(_table[i])
                    return iterator(_table[i], this);
            }
            return end();
        }

        iterator end()
        {
            return iterator(nullptr, this);
        }

        HashTable() : _n(0)
        {}

        HashTable(const HashTable<K, T, KeyOfT>& ht)
        {
            _table.resize(ht.size());
            for(int i = 0;i < ht.size();++i)
            {
                if(ht._table[i])
                {
                    HashNode<T>* cur = ht._table[i];
                    while(cur)
                    {
                        HashNode<T>* newnode = new HashNode<T>(cur->_val);
                        newnode->_next = _table[i];
                        _table[i] = newnode;
                        cur = cur->_next;
                    }
                }
            }
        }

        HashTable<K, T, KeyOfT>& operator=(HashTable<K, T, KeyOfT> ht)
        {
            _table.swap(ht._table);
            _n = ht._n;

            return *this;
        }

        std::pair<iterator, bool> insert(const T& kv)
        {
            KeyOfT kot;
            HashNode<T>* ret = find(kot(kv));
            if(ret)
                return std::make_pair(iterator(ret, this), false);     //节点已经存在了
            if(_n * 7 >= _table.size() * 10)
            {
                int capacity = _table.empty() ? default_capacity : 2 * _table.size();
                std::vector<HashNode<T>*> newHT;
                newHT.resize(capacity);
                for(int i = 0;i < newHT.size();++i)
                {
                    newHT[i] = nullptr;
                }
                for(int i = 0;i < _table.size();++i)
                {
                    if(_table[i])
                    {
                        HashNode<T>* cur = _table[i];
                        while(cur)
                        {
                            int index = kot(cur->_val) % capacity;
                            HashNode<T>* Next = cur->_next;
                            cur->_next = newHT[index];
                            newHT[index] = cur;
                            cur = Next;
                        }
                    }
                    _table[i] = nullptr;
                }
                _table.swap(newHT);
            }
            int index = kot(kv) % _table.size();
            HashNode<T>* newnode = new HashNode<T>(kv);
            newnode->_next = _table[index];
            _table[index] = newnode;
            ++_n;

            return std::make_pair(iterator(newnode, this), true);
        }

        HashNode<T>* find(const K& key)
        {
            if(_table.size() == 0)
                return nullptr;
            int index = key % _table.size();
            HashNode<T>* cur = _table[index];
            KeyOfT kot;
            while(cur)
            {
                if(kot(cur->_val) == key)
                    return cur;
                cur = cur->_next;
            }
            return nullptr; //没找到
        }

        bool erase(const T& kv)
        {   
            HashNode<T>* ret = find(kv.first);
            if(ret == nullptr)
                return false;   //节点不存在
            KeyOfT kot;
            int index = kot(kv) % _table.size();
            HashNode<T>* cur = _table[index];
            HashNode<T>* pre = nullptr;
            --_n;
            if(kot(cur->_val) == kot(kv)) //目标节点为头节点
            {
                _table[index] = cur->_next;
                delete cur;
                return true;
            }
            while(kot(cur->_val) != kot(kv))
            {
                pre = cur;
                cur = cur->_next;
            }
            pre->_next = cur->_next;
            delete cur;

            return true;
        }

        void Print()
        {
            for(int i = 0;i < _table.size();++i)
            {
                if(_table[i])
                {
                    HashNode<T>* cur = _table[i];
                    while(cur)
                    {
                        //std::cout << cur->_val.first << " : " << cur->_val.second << std::endl;
                        std::cout << cur->_val << std::endl;
                        cur = cur->_next;
                    }
                }
            }
        }

        int size() const 
        {
            return _table.size();
        }

        ~HashTable()
        {
            for(int i = 0;i < size();++i)
            {
                if(_table[i])
                {
                    HashNode<T>* cur = _table[i];
                    while(cur)
                    {
                        HashNode<T>* Next = cur->_next;
                        delete cur;
                        cur = Next;
                    }
                    _table[i] = nullptr;
                }
            }
        }
    public:
        std::vector<HashNode<T>*> _table;
        int _n;                           
    };
};